home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / graphics.swg / 0156_Voxel-Graphics Explained.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1995-03-26  |  8.3 KB  |  195 lines
  1. {
  2. >   Can someone explain the details of how to make game graphics like
  3. >   in commanche over kill ?
  4.  
  5. It's called Voxel. Don't ask me why. Below is a text that explains it.
  6.  
  7. ---------------------------------------------------------------
  8. From: pleung@cs.buffalo.edu (Patrick Leung)
  9.  
  10. Newsgroups: rec.games.programmer
  11. Subject: How To: Mars Landscape (Repost)
  12.  
  13. Well, since I posted something about the: 'Voxel landscapes and
  14. How I did it' post by Tim Clarke, a coupla people have asked about
  15. it. So, here it is, Tim Clarke's : Voxel landscapes and How I did it
  16. with some corrections and modifications he added in later postings.
  17. Hope I dont infringe on any of his rights in doing this...
  18.  
  19. The 'I' s in the following represent Tim Clarke, not me :)
  20.  
  21.         Voxel landscapes and How I did it
  22.         ---------------------------------
  23.  
  24.  This document describes the method I used in my demo of a Martian terrain,
  25. which can be found at garbo.uwasa.fi:/pc/demo/mars10.zip.
  26.  It's similar to a floating horizon hidden line removal algorithm, so you'll
  27. find discussion of the salient points in many computer graphics books. The
  28. difference is the vertical line interpolation.
  29.  
  30.  
  31. First, some general points:
  32. ---------------------------
  33.  
  34.  The map is a 256x256 grid of points, each having an 8-bit integer height
  35. and a colour. The map wraps round such that, calling w(u,v) the height at
  36. (u,v), then w(0,0)=w(256,0)=w(0,256)=w(256,256). w(1,1)=w(257,257), etc.
  37.  
  38.  Map co-ords: (u,v) co-ordinates that describe a position on the map. The
  39. map can be thought of as a height function h=w(u,v) sampled discretely.
  40.  
  41.  Screen co-ords: (x,y) co-ordinates for a pixel on the screen.
  42.  
  43.  
  44. To generate the map:
  45. --------------------
  46.  
  47.  This is a recursive subdivision, or plasma, fractal. You start of with
  48. a random height at (0,0) and therefore also at (256,0), (0,256), (256,256).
  49. Call a routine that takes as input the size and position of a square, in the
  50. first case the entire map.
  51.  This routine get the heights from the corners of the square it gets given.
  52. Across each edge (if the map has not been written to at the point halfway
  53. along that edge), it takes the average of the heights of the 2 corners on that
  54. edge, applies some noise proportional to the length of the edge, and writes
  55. the result into the map at a position halfway along the edge. The centre of
  56. the square is the average of the four corners+noise.
  57.  The routine then calls itself recursively, splitting each square into four
  58. quadrants, calling itself for each quadrant until the length of the side is
  59. 2 pixels.
  60.  This is probably old-hat to many people, but the map is made more realistic
  61. by blurring:
  62.  
  63.      w(u,v)=k1*w(u,v)+k2*w(u+3,v-2)+k3*w(u-2,v+4) or something.
  64.  
  65.  Choose k1,k2,k3 such that k1+k2+k3=1. The points at which the map is sampled
  66. for the blurring filter do not really matter - they give different effects,
  67. and you don't need any theoretical reason to choose one lot as long as it
  68. looks good. Of course do everything in fixed point integer arithmetic.
  69.  The colours are done so that the sun is on the horizon to the East:
  70.  
  71.      Colour=A*[ w(u+1,v)-w(u,v) ]+B
  72.  
  73. with A and B chosen so that the full range of the palette is used.
  74.  The sky is a similar fractal but without the colour transformation.
  75.  
  76.  
  77. How to draw each frame
  78. ----------------------
  79.  
  80.  First, draw the sky, and blank off about 50 or so scan lines below the
  81. horizon since the routine may not write to all of them (eg. if you are on top
  82. of a high mountain looking onto a flat plane, the plane will not go to the
  83. horizon).
  84.  Now, down to business. The screen is as follows:
  85.  
  86.      ---------------------------
  87.      |                         |
  88.      |                         |
  89.      |           Sky           |
  90.      |                         |
  91.      |                         |
  92.      |a------------------------| Horizon
  93.      |                         |
  94.      |                         |    Point (a)=screen co-ords (0,0)
  95.      |          Ground         |     x increases horizontally
  96.      |                         |     y increases downwards
  97.      |                         |
  98.      ---------------------------
  99.  
  100.  Imagine the viewpoint is at a position (p,q,r) where (p,q) are the (u,v)
  101. map co-ordinates and r is the altitude. Now, for each horizontal (constant v)
  102. line of map from v=q+100 (say) down to v=q, do this:
  103.  
  104.   1. Calculate the y co-ordinate of map co-ord (p,v,0) (perspective transform)
  105.  
  106.  
  107.     you:->------------------------ Horizontal view
  108.          :
  109.       r  :
  110.          :
  111.          :
  112.      -----------------------------P Ground
  113.          ......................... (q-v)
  114.          q                       v
  115.  
  116.  You have to find where the line between P and you intersects with the
  117. screen (vertical, just in front of 'you'). This is the perspective transform:
  118.    y=r/(q-v).
  119.  
  120.   2. Calculate scale factor f which is how many screen pixels high a mountain
  121. of constant height would be if at distance v from q. Therefore, f is small
  122. for map co-ords far away (v>>q) and gets bigger as v comes down towards q.
  123.  
  124.   So, f is a number such that if you multiply a height from the map by f, you
  125. get the number of pixels on the screen high that height would be. For
  126. example, take a spot height of 250 on the map. If this was very close, it
  127. could occupy 500 pixels on the screen (before clipping)->f=2.
  128.  
  129.   3. Work out the map u co-ord corresponding to (0,y). v is constant along
  130. each line.
  131.  
  132.   4. Starting at the calculated (u,v), traverse the screen, incrementing the
  133. x co-ordinate and adding on a constant, c, to u such that (u+c,v) are the map
  134. co-ords corresponding to the screen co-ords (1,y). You then have 256 map
  135. co-ords along a line of constant v. Get the height, w, at each map co-ord and
  136. draw a spot at (x,y-w*f) for all x.
  137.  
  138.  I.e. the further away the scan line is, the more to the "left" u will start,
  139. and the larger c will be (possibly skipping some u columns if c > 1); the
  140. closer the scan line, the lesser u will start on the "left", and c will be
  141. smaller.
  142.  
  143.  
  144.  Sorry, but that probably doesn't make much sense. Here's an example:
  145. Imagine sometime in the middle of drawing the frame, everything behind a
  146. point (say v=q+50) will have been drawn:
  147.  
  148.      ---------------------------
  149.      |                         |
  150.      |                         |
  151.      |                         |
  152.      |           ****          |
  153.      |        *********        | <- A mountain half-drawn.
  154.      |-----**************------|
  155.      |*************************|
  156.      |*********       *********|
  157.      |******             ******|
  158.      |.........................| <- The row of dots is at screen co-ord y
  159.      |                         |   corresponding to an altitude of 0 for that
  160.      ---------------------------   particular distance v.
  161.  
  162.  Now the screen-scanning routine will get called for v=q+50. It draws in a
  163. point for every x corresponding to heights at map positions (u,v) where u
  164. goes from p-something to p+something, v constant. The routine would put points
  165. at these positions: (ignoring what was there before)
  166.  
  167.      ---------------------------
  168.      |                         |
  169.      |                         |
  170.      |                         |
  171.      |                         |
  172.      |                         |
  173.      |-------------------------|
  174.      |          *****          |
  175.      |       ***     ***       |
  176.      |*******           *******|
  177.      |.........................|
  178.      |                         |
  179.      ---------------------------
  180.  
  181.  So, you can see that the screen gets drawn from the back, one vertical
  182. section after another. In fact, there's more to it than drawing one pixel
  183. at every x during the scan - you need to draw a vertical line between
  184. (x,y old) to (x,y new), so you have to have a buffer containing the y values
  185. for every x that were calculated in the previous pass. You interpolate
  186. along this line (Gouraud style) from the old colour to the new colour also,
  187. so you have to keep a buffer of the colours done in the last pass.
  188.  Only draw the vertical lines if they are visible (ie. going down,
  189. y new>y old). The screen is drawn from the back so that objects can be drawn
  190. inbetween drawing each vertical section at the appropriate time.
  191.  
  192.  If you need further information or details, mail me or post here... Posting
  193. will allow others to benefit from your points and my replies, though.
  194.  
  195.